package com.LeetCode.Tree;

import com.nowcoder.Offer.List.ListNode;
import org.junit.Test;

/**
 * 二叉树最大路径和
 */
public class MaxPathSum {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode root){
        if(root == null)
            return 0;

        int leftGain = Math.max(maxGain(root.left) , 0);
        int rightGain = Math.max(maxGain(root.right), 0);

        int curSum = leftGain + root.val + rightGain;
        maxSum = Math.max(maxSum, curSum);

        return root.val + Math.max(leftGain, rightGain);
    }

    @Test
    public void test(){
        TreeNode node1 = new TreeNode(-10);
        TreeNode node2 = new TreeNode(9);
        TreeNode node3 = new TreeNode(20);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(7);
    }
}
